package coursera.assignments;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.List;

import org.apache.commons.lang3.StringUtils;

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Lists;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multiset.Entry;
import com.google.common.collect.Ordering;


/**
 * JVM params to run with: -Xms9999m -Xmx9999m -Xss9999m
 * 
 * @author takkars (Sachin Takkar)
 * 
 */
public class AlgorithmsProblem4StronglyConnectedComponents {

    public static int VERTEX_AMOUNT = 875714;
    public static int LINES_AMOUNT = 5105043;

    private UndirectedGraph graph;

    private int counter = 0;
    private int currentLeaderVertex = -1;

    private boolean visited[];
    private int leaders[];
    private int finishingTime[];
    private int finishingTimeReversed[];

	public static void main(String[] args) throws IOException {
    	
    	AlgorithmsProblem4StronglyConnectedComponents scc = new AlgorithmsProblem4StronglyConnectedComponents();
    	
        scc.graph = scc.readGraph(VERTEX_AMOUNT, LINES_AMOUNT);

        scc.dfs1Loop();
        scc.dfs2Loop();

        List<Integer> result = scc.sortedSizes(5);
        System.out.println(StringUtils.join(result, ","));
    }

    public UndirectedGraph readGraph(int n, int l) throws IOException {
        UndirectedGraph graph = new UndirectedGraph(n);

        FileReader fr = null;
		BufferedReader br = null;
		try {
			fr = new FileReader("SCC.txt");
			br = new BufferedReader(fr);
			String line;
			for (int i=0;(line = br.readLine()) != null;i++) {
				String[] split = line.trim().split("(\\s)+");
				graph.addEdge(Integer.valueOf(split[0])-1, Integer.valueOf(split[1])-1);
	            if (i % 1000 == 0) {
	                System.out.println(i + "th has been just processed");
	            }
			}
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			br.close();
		}

        return graph;
    }

    public void dfs1Loop() {
        visited = new boolean[graph.getN()];
        finishingTime = new int[graph.getN()];
        Arrays.fill(finishingTime, -1);
        finishingTimeReversed = new int[graph.getN()];
        Arrays.fill(finishingTimeReversed, -1);

        for (int i = graph.getN() - 1; i >= 0; i--) {
            if (!visited[i]) {
                currentLeaderVertex = i;
                dfs1(i);
            }
        }
    }

    private void dfs1(int u) {
        visited[u] = true;

        for (int v : graph.reverse(u)) {
            if (!visited[v]) {
                dfs1(v);
            }
        }

        finishingTime[u] = counter;
        finishingTimeReversed[counter] = u;
        counter++;
    }

    public void dfs2Loop() {
        visited = new boolean[graph.getN()];
        leaders = new int[graph.getN()];
        Arrays.fill(leaders, -1);

        for (int i = graph.getN() - 1; i >= 0; i--) {
            int ft = finishingTimeReversed[i];
            if (!visited[ft]) {
                currentLeaderVertex = ft;
                dfs2(ft);
            }
        }
    }

    private void dfs2(int u) {
        visited[u] = true;
        leaders[u] = currentLeaderVertex;

        for (int v : graph.adjacent(u)) {
            if (!visited[v]) {
                dfs2(v);
            }
        }
    }

    public void setGraph(UndirectedGraph graph) {
        this.graph = graph;
    }

    public int[] getFinishingTime() {
        return finishingTime;
    }

    public int[] getLeaders() {
        return leaders;
    }

    public List<Integer> sortedSizes(int desiredSize) {
        List<Integer> result = sort(countFrequencies());

        if (desiredSize <= result.size()) {
            return result.subList(0, desiredSize);
        } else {
            return addUpZeros(desiredSize, result);
        }
    }

    private static List<Integer> sort(List<Integer> result) {
        Ordering<Integer> ordering = Ordering.natural().reverse();
        return ordering.sortedCopy(result);
    }

    private List<Integer> countFrequencies() {
        Multiset<Integer> distinctLeaders = distinctLeaders();
        List<Integer> result = Lists.newArrayList();

        for (Entry<Integer> entry : distinctLeaders.entrySet()) {
            result.add(entry.getCount());
        }
        return result;
    }

    public Multiset<Integer> distinctLeaders() {
        Multiset<Integer> result = HashMultiset.create();
        for (int i : leaders) {
            result.add(i);
        }
        return result;
    }

    private static List<Integer> addUpZeros(int desiredSize, List<Integer> result) {
        List<Integer> newResult = Lists.newArrayList(result);
        int n = desiredSize - result.size();
        while (n > 0) {
            newResult.add(0);
            n--;
        }
        return newResult;
    }
}